﻿/*
题目：推箱子

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 '.' 表示，意味着可以自由行走。
墙用字符 '#' 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // 广度优先搜索
    // **KEY** 人在推到箱子前类似于DFS，每次不断把人的状态加入到队头，而推到箱子后是BFS
    // **KEY** 关键就在于 “状态“ 的 **递推**
    //
    // 每次从 deque 里面取出一个元素/状态，来往前推进，如果是空白处，那么放到队头，相当于 dfs，来找到箱子
    // 如果 往前推进是箱子，那么放到队尾，相当于 bfs，就是最短搜索路径
    // 然后一个 vis[][] 来记录 状态A -> 状态B 是否被访问过
    int minPushBox(vector<vector<char>>& grid) {
        static int dirs[] = { 0, -1, 0, 1, 0 };
        int N = grid.size(), M = grid[0].size();

        auto ok = [&grid, &N, &M](int x, int y) { return x >= 0 && x < N&& y >= 0 && y < M&& grid[x][y] != '#'; };
        auto xoy = [&N, &M](int x, int y) { return x * M + y; };

        int bx, by, sx, sy;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 'S') {
                    sx = i;
                    sy = j;
                }
                else if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                }
            }
        }

        // 表示从 一个状态 到 另一个状态 所需的最少操作数
        deque<tuple<int, int, int>> deq;
        // 从 一个状态 到 另一个状态 是否被访问过
        vector<vector<bool>> vis(N * M, vector<bool>(N * M, false));
        deq.emplace_back(xoy(sx, sy), xoy(bx, by), 0);
        vis[xoy(sx, sy)][xoy(bx, by)] = true;

        while (!deq.empty()) {
            auto [src, dst, steps] = deq.front();
            deq.pop_front();

            int srcx = src / M, srcy = src % M;
            int dstx = dst / M, dsty = dst % M;
            if (grid[dstx][dsty] == 'T')    return steps;

            for (int i = 0; i < 4; i++) {
                int nx = srcx + dirs[i], ny = srcy + dirs[i + 1];
                if (!ok(nx, ny))    continue;

                // 下一步就是箱子
                if (nx == dstx && ny == dsty) {
                    int nnx = nx + dirs[i], nny = ny + dirs[i + 1];
                    if (!ok(nnx, nny) || vis[xoy(nx, ny)][xoy(nnx, nny)] == true)
                        continue;
                    deq.emplace_back(xoy(nx, ny), xoy(nnx, nny), steps + 1);
                    vis[xoy(nx, ny)][xoy(nnx, nny)] = true;
                }
                else {  // not the box
                    if (vis[xoy(nx, ny)][dst] == true)  continue;
                    deq.emplace_front(xoy(nx, ny), dst, steps);
                    vis[xoy(nx, ny)][dst] = true;
                }
            }
        }

        return -1;
    }
};

